package offer2

/**
原题链接:
https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

B站 帅地玩编程
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
并保证奇数和奇数，偶数和偶数之间的相对位置不变。

示例1
输入：[1,2,3,4]
返回值：[1,3,2,4]

示例2
输入：[2,4,6,5,7]
返回值：[5,7,2,4,6]

示例3
输入：[1,3,5,6,7]
返回值：[1,3,5,7,6]
*/

func reOrderArray(array []int) []int {

	right := 0 //确定奇数元素个数
	for i := 0; i < len(array); i++ {
		if array[i]&1 == 1 {
			right++
		}
	}

	left := 0
	ret := make([]int, len(array))

	for i := 0; i < len(array); i++ {
		if array[i]&1 == 1 { // 如果是奇数则存储到前半部分
			ret[left] = array[i]
			left++
		} else {
			ret[right] = array[i] //是偶数，存储在后半部分
			right++
		}
	}

	return ret
}
